from heapq import heappush, heappop
import random

# A* pseudocode from Wikipedia, 18.06.2008
#   The Wikipedia example has since been "improved" to the point of
#   uselessness, so I'm keeping this handy.
#
# function A*(start,goal)
#     var closed := the empty set
#     var q := make_queue(path(start))
#     while q is not empty
#         var p := remove_first(q)
#         var x := the last node of p
#         if x in closed
#             continue
#         if x = goal
#             return p
#         add x to closed
#         foreach y in successors(x)
#             enqueue(q, p, y)
#     return failure

# This code is a bit messy and contains a lot of implementations
# of various variants on uniform-cost search.

blocked = "infinite"
	# return this as blocked as the "cost" instead of a number
	# if it is simply impossible to enter the tile in question.

class goalEquality:
	def __init__(self, x):
		self.x = x
	def __call__(self, y):
		return self.x == y

class goalPoint:
	def __init__(self, p):
		self.x, self.y = p
	def __call__(self, p):
		return self.x == p[0] and self.y == p[1]

class heuristicPointEuclidean:
	def __init__(self, p):
		self.x, self.y = p
	def __call__(self, p):
		from math import sqrt
		x, y = p
		dx, dy = self.x-x,self.y-y
		return sqrt( dx*dx + dy*dy )

class heuristicPointRoguelike:
	def __init__(self, p):
		self.x, self.y = p
	def __call__(self, p):
		x, y = p
		return max( abs(self.x-x), abs(self.y-y) )

def heuristicZero(p):
	return 0

class goalSet:
	def __init__(self, goalset):
		self.goalset = set(goalset)
	def __call__(self, p):
		return p in self.goalset

class PathTail:
	def __init__(self, path, transitionPrice, skip):
		goalset = set()
		goalset.add( path[-1] )
		totalCost = 0
		target = path[-1]
		for i in range(len(path)-1): #ignores last element
			if totalCost >= skip:
				if path[-1] == target:
					target = path[i]
				goalset.add( path[i] )
			else:
				totalCost += transitionPrice( path[i], path[i+1] )
		self.goal = goalSet( goalset )
		self.heuristic = heuristicPointRoguelike( target )


def successors2dGrid(p):
	x,y = p
	rv = [ (x+i,y+j) for i in (-1,0,1) for j in (-1,0,1) if i or j ]
	#random.shuffle( rv )
	return rv
	#return [ (x+i,y+j) for i in (-1,0,1) for j in (-1,0,1) if i or j ]

class Pathfinder:
	def __init__(self, goal, evaluatePath, heuristic = heuristicZero, successors = successors2dGrid):
		self.open = [] # heapq of (priority, tiebreaker, path)
		self.closed = []
		self.heuristic = heuristic
		self.goal = goal
		self.evaluatePath = evaluatePath
		self.successors = successors
	def addStart(self, p):
		heappush( self.open, ( self.heuristic(p), 0, (p,) ) )
	def findPath(self):
		while self.open:
			priority, tiebreaker, path = heappop(self.open)
			if path[-1] in self.closed:
				continue
			if self.goal( path[-1] ):
				return path
			self.closed.append( path[-1] )
			for next in self.successors( path[-1] ):
				pathPrime = path + (next,)
				#transitionPrice = self.price( pathPrime )
				#if transitionPrice == blockedPrice: continue
				#costPrime = cost + transitionPrice
				costPrime, tiebreaker = self.evaluatePath( pathPrime )
				if costPrime  == blocked: continue
				priorityPrime = costPrime + self.heuristic( next )
				heappush( self.open, (priorityPrime,tiebreaker,pathPrime) )
		return None

class Waypoint:
	def __init__(self, point):
		self.parent = None # will be "adopted" later
		self.x, self.y = point
		self.links = {} # point -> cost, path
	def transform(self):
		oldLinks = self.links
		self.links = {}
		for key, value in oldLinks.items():
			wp = self.parent.waypoints[ key ]
			self.links[ wp ] = value
	def __str__(self):
		return "<%d,%d>" % (self.x, self.y)
	def __repr__(self):
		return "Waypoint((%d,%d))" % (self.x, self.y)

class heuristicWaypointExact:
	def __init__(self, target):
		self.waypoints = target.parent
		self.targetPoint = (target.x, target.y)
	def __call__(self, waypoint):
		index = tuple( sorted( [ (waypoint.x,waypoint.y) , self.targetPoint ] ) )
		return self.waypoints.distance[index]

def successorsWaypoint( waypoint ):
	return waypoint.links.keys()
	return [ waypoint.parent.waypoints[key] for key in waypoint.links.keys() ]

def evaluatePathWaypoint( waypointPath ):
	rv = 0
	for i in range( len(waypointPath ) - 1):
		rv += waypointPath[i].links[ waypointPath[i+1] ][0]
	return rv, 0

class goalAnyWaypoint:
	def __init__(self, waypoints):
		self.waypoints = waypoints
	def __call__(self, point):
		return self.waypoints.waypoints.has_key( point )		
class Waypoints:
	def __init__(self, waypoints):
		self.waypoints = waypoints
		self.distance = {} # lesserPoint, greaterPoint -> cost
	def findClosestWaypoint(self, point, evaluatePath, successors = successors2dGrid):
		pf = Pathfinder( goal = goalAnyWaypoint(self), evaluatePath = evaluatePath, heuristic = heuristicZero, successors = successors )
		pf.addStart( point )
		path = pf.findPath()
		wp = self.waypoints[ path[-1] ]
		return list(path), wp
	def findPathBetweenWaypoints(self, a, b):
		pf = Pathfinder( goal = goalEquality(b), evaluatePath = evaluatePathWaypoint, heuristic = heuristicWaypointExact( b ), successors = successorsWaypoint )
		pf.addStart( a )
		wppath = pf.findPath()
		if wppath:
			rv = [ (a.x, a.y) ]
			for i in range(len(wppath)-1):
				f, t = wppath[i:i+2]
				rv += list(f.links[t][1])
			return rv
		return None
	def findGeneralPath(self, a, b, evaluatePath, successors = successors2dGrid ):
		inpath, wpA = self.findClosestWaypoint( a, evaluatePath, successors )
		outpath, wpB = self.findClosestWaypoint( b, evaluatePath, successors )
		outpath.reverse()
		tweenpath = self.findPathBetweenWaypoints( wpA, wpB )
		rv = []
		for p in inpath + tweenpath + outpath:
			if p in rv:
				rv = rv[:rv.index(p)]
			rv.append( p )
		return rv

		
	def exploreFrom(self, start):
		q = []
		closed = set()
		heappush( q, (0,start) )
		i = 0
		while q:
			i += 1
			cost, point = heappop(q)
			if point in closed: continue
			closed.add( point ) 
			index = tuple( sorted( [point,start] ) )
				# this way each distance gets set twice,
				# but inefficiency in the startup computation time
				# shouldn't matter much
			self.distance[ index ] = cost
			links = self.waypoints[point].links
			for next in links.keys():
				if (next.x,next.y) in closed: continue
				heappush( q, (cost + links[next][0], (next.x,next.y) ) )
	def explore(self):
		for waypoint in self.waypoints.values():
			self.exploreFrom( (waypoint.x, waypoint.y) )

class WaypointBuilder:
	def __init__(self, width, height, tileCost, successors = successors2dGrid):
		# Should go: regions = .createRandomRegions()
		#	     create evenly spaced waypoints & addPoint(), e.g. by
		#	      darkest() and lightProximity() (remember to light
		#	      up the region waypoints created above first)
		#            .freezeWaypoints()
		#            .buildClosenessWeb( range )
		#	     .ensureConnectedness( regions )
		#	     waypoints = .transform()
		# Closeness range is advised to be twice the beacon cutoff if
		#  lightProximity is used.
		# You should add a sufficient number of waypoints to make the
		#  character only have to path about 30 spaces at most to get
		#  to a waypoint.
		# You should NOT rely on .ensureConnectedness() for anything
		#  beyond connecting things that were left unconnected because
		#  of statistical flukes; if the graph is thoroughly disconnected,
		#  .ensureConnectedness() will leave only a very minimal web
		#  after a very long time.
		self.width, self.height = width, height
		self.tileCost = tileCost # "blocked" tiles are ignored
		self.successors = successors
		self.needsConnection = set( [ (x,y) for x in range(self.width) for y in range(self.height) if self.tileCost( (x,y) ) != blocked ] )
		self.points = set()
	def transform(self):
		rv = Waypoints( self.waypoints )
		for wp in self.waypoints.values():
			wp.parent = rv
			wp.transform()
		rv.explore()
		return rv
	def markConnectedRegion(self, point):
		q = [ point ]
		self.needsConnection.remove( point )
		while q:
			p = q.pop(0)
			for n in self.successors(p):
				if self.tileCost(n) != blocked and n in self.needsConnection:
					self.needsConnection.remove( n )
					q.append( n )
	def createRandomRegions(self):
		rv = []
		while self.needsConnection:
			rv.append( random.choice( list(self.needsConnection ) ) )
			self.addPoint( rv[-1] )
			self.markConnectedRegion( rv[-1] )
		return rv
	def freezeWaypoints(self):
		self.waypoints = {}
		for point in self.points:
			self.waypoints[point] = Waypoint( point )
	def partiallyConnectGraph(self, beginnings, ends ):
		q = []
		closed = set()
		for beginning in beginnings:
			heappush( q, (0, (beginning,)) )
		while ends:
			cost, path = heappop(q)
			point = path[-1]
			startWaypoint = path[0]
			if (point,startWaypoint) in closed: continue
			closed.add( (point,startWaypoint) )
			if point in ends:
				self.waypoints[ startWaypoint ].links[ point ] = cost, path
				self.waypoints[ point ].links[ startWaypoint ] = cost, list(reversed(path))
				return
			else:
				for next in self.successors( point ):
					if (next,startWaypoint) in closed: continue
					tc = self.tileCost( next )
					if tc == blocked: continue
					heappush( q, (cost + tc, path + (next,) ) )
	def buildCloseness(self, origin, costLimit):
		# expand until we find either all waypoints within the
		# given cost, or have found all the protolinks, whichever comes
		# last.
		p = origin.x, origin.y
		q = []
		heappush( q, (0,p, None) )
		prev = {}
		visited = set()
		while q:
			cost, point, pnode = heappop(q)
			if cost > costLimit: continue
			if point in visited: continue
			visited.add( point )
			prev[point] = pnode
			if self.waypoints.has_key( point ):
				path = []
				cn = point
				while prev[cn]:
					path.append( cn )
					cn = prev[cn]
				path.reverse()
				origin.links[ point ] = cost, path
			for next in self.successors( point ):
				tc = self.tileCost( next )
				if tc == blocked: continue
				nc = cost + tc
				if nc > costLimit: continue
				if next in visited: continue
				heappush( q, (nc, next, point ) )
	def buildClosenessWeb(self, costLimit):
		import time
		for origin in self.waypoints.values():
			self.buildCloseness( origin, costLimit )
	def addPoint(self, p):
		self.points.add( p )
	def prepareProximity(self):
		self.proximity = []
		self.darkness, self.darknessCount = 0, 0
		for i in range(self.width):
			l = []
			for j in range(self.height):
				if self.tileCost( (i,j) ) == blocked:
					l.append( None )
				else:
					l.append( 0 )
					self.darknessCount += 1
			self.proximity.append( l )
	def lightProximity(self, origin, cutoff):
		q = []
		closed = set()
		heappush( q, (0,origin) )
		i = 0
		while q:
			i += 1
			cost, point = heappop( q )
			if point in closed: continue
			closed.add( point )
			x, y = point
			if self.proximity[x][y] == self.darkness:
				self.darknessCount -= 1
			if not cost:
				self.proximity[x][y] += 10**9 
			else:
				self.proximity[x][y] += 1.0 / (cost*cost)
			for next in self.successors( point ):
				tileCost = self.tileCost( next ) 
				if tileCost == blocked: continue
				newCost = cost + tileCost
				if newCost > cutoff: continue
				heappush( q, (newCost, next ) )
	def darkest(self):
		# Waaay overcomplicated. This was done to remove a bottleneck when processing
		# for maps the size of moo's overworld (approx. 800x500).
		import random
		darknessReps = []
		maxReps = 20
		if self.darknessCount <= 0:
			self.darkness = 10 ** 12
			self.darknessCount = 0
			for x in range(self.width):
				for y in range(self.height):
					if self.proximity[x][y] != None and self.proximity[x][y] < self.darkness:
						self.darkness = self.proximity[x][y]
						self.darknessCount = 0
						darknessReps = [ (x,y) ]
					if self.proximity[x][y] == self.darkness:
						self.darknessCount += 1
						if len(darknessReps) < maxReps: darknessReps.append( (x,y) )
		if darknessReps and self.darknessCount == len(darknessReps):
			return random.choice( darknessReps )
		elif self.darknessCount * 10 > (self.width*self.height):
			while True:
				x = random.randint(0,self.width-1)
				y = random.randint(0,self.height-1)
				if self.proximity[x][y] != self.darkness: continue
				return (x,y)
		else:
			i0 = i = random.randint(0,self.darknessCount-1)
			for x in range(self.width):
				for y in range(self.height):
					if self.proximity[x][y] == self.darkness:
						if not i: return (x,y)
						i -= 1
	def ensureConnectedness(self, regionPoints):
		while True:
			disco = self.findDisconnecteds( regionPoints )
			if not disco: break
			goals = self.waypoints.keys()
			self.partiallyConnectGraph( disco, [ p for p in self.waypoints.keys() if not p in disco ] )
	def findDisconnecteds(self, regionPoints):
		goals = self.waypoints.keys()
		q = []
		for point in regionPoints:
			q.append( point )
		while q:
			point = heappop(q)
			wp = self.waypoints[point]
			if point in goals:
				goals.remove( point )
			else: continue
			for link in wp.links.keys():
				if not link in goals: continue
				q.append( link )
		return goals
